Advances in computer hardware and software technology have brought about increasing uses of digital imagery. However, the amount of memory necessary to store a large number of high resolution digital images is significant. Furthermore, the time and bandwidth necessary to transmit the images is unacceptable for many applications. Accordingly, there has been considerable interest in the field of digital image compression.
The basic elements of a digital image compression system are shown schematically in FIG. 1, and are referenced by those elements contained within dotted line box 100. A digitized image is processed by an encoder 101 to reduce the amount of information required to reproduce the image. This information is then typically stored as compressed data in a memory 102. When the image is to be reconstructed, the information stored in memory 102 is passed through a decoder 103.
The goal of a good compression method implemented by encoder 101 is to attain a high compression ratio with minimal loss in fidelity. One of the latest approaches to the image compression problem has been put forth by Arnaud Jacquin in a paper entitled "Fractal Image Coding Based on a Theory of Iterated Contractive Image Transformations", appearing in The International Society for Optical Engineering Proceedings Volume 1360, Visual Communications and Image Processing, October 1990, pp. 227-239.
As is known in the art, fractal image generation is based on the iteration of simple deterministic mathematical procedures that can generate images with infinitely intricate geometries (i.e. fractal images). However, to use these fractal procedures in digital image compression, the inverse problem of constraining the fractal complexity to match the given complexity of a real-world image must be solved. The "iterated transformation" method of Jacquin constructs, for each original image, a set of transformations which form a map that encodes the original image. Each transformation maps a portion of the image (known as a domain) to another portion of the image (known as a range). The transformations, when iterated, produce a sequence of images which converge to a fractal approximation of the original image.
In order for a transformation to map onto some portion of the original image within a specified error bound, the transformation must be optimized in terms of position, size and intensity. If the transformation cannot be optimized within the specified error bound for a given set of ranges and domains, predefined subdivisions of the ranges are selected. The search for an optimized transformation then continues using these subdivisions. One method of predefining the subdivisions is known as quad-tree partitioning which divides a square sized range in a fixed way. Essentially, the range is subdivided into four equally sized squares without considering any of the image's features.
Thus, the need exists for a method of adaptively partitioning the image in an iterated transformation system based upon the features of the image. Accordingly, it is an object of the present invention to provide a method of encoding a digital image in an iterated transformation system by using adaptive partitioning in determining suitable ranges and domains to encode the image. Another object of the present invention is to provide a method of encoding a digital image in an iterated transformation system that adjusts to the features of the image during its partitioning process.